package main;

import ch08.*;

public class Main {
    private static final int INFINITY =Integer.MAX_VALUE ;


    public static void main(String[] args) throws Exception {
        SqList L = new SqList(10);
        L.insert(0, "城市A");
        L.insert(1, "城市B");
        L.insert(2, "城市C");
        L.insert(3, "城市D");
        L.insert(4, "城市E");
        L.insert(5, "城市F");
        L.insert(6, "城市G");
        L.insert(7, "城市H");
        L.insert(8, "城市I");
        L.insert(9, "城市J");
        L.display();


        Object vex1[] = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
        int[][] arcs1 = {{0, INFINITY, INFINITY, 3, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, 0, 4, INFINITY, INFINITY, INFINITY, INFINITY, 5, INFINITY, INFINITY},
                {INFINITY, 4, 0, INFINITY, 6, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY},
                {3, INFINITY, INFINITY, 0, INFINITY, INFINITY, 2, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, 6, INFINITY, 0, 1, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, 1, 0, INFINITY, INFINITY, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, 2, INFINITY, INFINITY, 0, 7, 8, 9},
                {INFINITY, 5, INFINITY, INFINITY, INFINITY, INFINITY, 7, 0, INFINITY, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 8, INFINITY, 0, INFINITY},
                {INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, INFINITY, 9, INFINITY, INFINITY, 0},

        };

        System.out.println("最小生成树：  ");
        MGraph G0 = new MGraph(GraphKind.UDN, 10, 9, vex1, arcs1);
        Object[][] tree0 = new MiniSpanTree().PRIM(G0, "A");
        for (int i = 0; i < tree0.length; i++)
            System.out.println(tree0[i][0] + "-" + tree0[i][1]);


        MGraph G = new MGraph(GraphKind.UDN, 10, 9, vex1, arcs1);
        ShortestPath_FLOYD floyd = new ShortestPath_FLOYD();
        floyd.FLOYD(G);
        display(floyd.getD());
        findPlace(G, floyd.getD());


        int start = 0;
            int[] shortPath = dijkstra(arcs1, start);

            //for (int i = 0; i < shortPath.length; i++)
            //System.out.println("从" + start + "出发到" + i + "的最短距离为：" + shortPath[i]);

    }
    public static int[] dijkstra(int[][] arcs1, int start) {
        // 接受一个有向图的权重矩阵，和一个起点编号start（从0编号，顶点存在数组中）
        // 返回一个int[] 数组，表示从start到它的最短路径长度
        int n = arcs1.length; // 顶点个数
        int[] shortPath = new int[n]; // 保存start到其他各点的最短路径
        String[] path = new String[n]; // 保存start到其他各点最短路径的字符串表示
        for (int i = 0; i < n; i++)
            path[i] = new String(start + "-->" + i);
        int[] visited = new int[n]; // 标记当前该顶点的最短路径是否已经求出,1表示已求出

        // 初始化，第一个顶点已经求出
        shortPath[start] = 0;
        visited[start] = 1;

        for (int count = 1; count < n; count++) { // 要加入n-1个顶点
            int k = -1; // 选出一个距离初始顶点start最近的未标记顶点
            int dmin = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (visited[i] == 0 && arcs1[start][i] < dmin) {
                    dmin = arcs1[start][i];
                    k = i;
                }
            }

            // 将新选出的顶点标记为已求出最短路径，且到start的最短路径就是dmin
            shortPath[k] = dmin;
            visited[k] = 1;

            // 以k为中间点，修正从start到未访问各点的距离
            //重写
            for (int i = 0; i < n; i++) {
                //如果 '起始点到当前点距离' + '当前点到某点距离' < '起始点到某点距离', 则更新
                if (visited[i] == 0 && arcs1[start][k] + arcs1[k][i] < arcs1[start][i]) {
                    arcs1[start][i] = arcs1[start][k] + arcs1[k][i];
                    path[i] = path[start] + "-->" + path[k]+"-->"+i;
                }
            }
        }
        for (int i = 0; i < n; i++) {

            System.out.println("从" + start + "出发到" + i + "的最短路径为：" + path[i]);
        }
        System.out.println("=====================================");
        return shortPath;
    }

    public static void display(int[][] D){
        System.out.println("各城市之间的最短路径为： ");
        for(int v=0;v<D.length;v++) {
            for (int w = 0; w < D.length; w++)
                System.out.print(D[v][w] + "   ");
                System.out.println();
        }
        System.out.println("=====================================");
            int i=-1;
            for (int w = 0; w < D.length; w++){
                i++;
                System.out.println("从0出发到" + i+"的最短距离"+D[0][w]);
            }
            System.out.println();
    }
    public static void findPlace(MGraph G, int[][] D)throws Exception{
        int min =INFINITY;
        int sum = 0;
        int u =-1;
        for (int v=0;v<D.length;v++){
            sum = 0;
            for (int w=0;w<D.length;w++)
                sum +=  D[v][w];
            if (min>sum){
                min =sum;
                u =v;
            }
        }
        System.out.println("维修中心应设在"+G.getVex(u)+"处，其余各处的路径长度为：");
        for (int i=0;i<D.length;i++)
            System.out.print(D[u][i]+"\t");
        System.out.println();
    }






}





